package com.leetcode.No0038;

import org.junit.Test;

import java.util.*;

/**
 * @program: leetcode
 * @description: 字符串的排列
 * @author: wangzhihua
 * @date: 2021-07-09
 */
public class Solution01 {

	@Test
	public void test01() {
		System.out.println(Arrays.toString(permutation("abcdefgg")));
	}
	private final int[] FACTORIAL = new int[]{0, 1, 2, 6, 24, 120, 720, 5040, 40320};

	private int totalNum;
	private StringBuilder sb;
	private char[] charArray;
	private boolean[] isUsed;
	private Set<String> strSet;

	public String[] permutation(String s) {
		// 准备工作
//		HashSet<Character> charSet = new HashSet<Character>();
//		for (Character ch : s.toCharArray()) {
//			charSet.add(ch);
//		}
//		charArray = charSet.toArray(new Character[0]);
		charArray = s.toCharArray();
		totalNum = charArray.length;
		sb = new StringBuilder(totalNum);
		isUsed = new boolean[totalNum];
		strSet = new HashSet<String>();

		// 递归地对所有字符进行排列组合
		iteration(1);

		return strSet.toArray(new String[0]);
	}

	public void iteration(int currentNum) {
		if (currentNum > totalNum) {
			strSet.add(sb.toString());
			return;
		}
		for (int i = 0; i < totalNum; ++i) {
			if (!isUsed[i]) {
				isUsed[i] = true;
				sb.append(charArray[i]);
				iteration(currentNum + 1);
				isUsed[i] = false;
				sb.deleteCharAt(sb.length() - 1);
			}
		}
	}

}
